package chapter_05;

// 双端链表
/*
双端链表允许在表尾插入一个链接点。当然，仍然可以在普通的单链表的表尾插入一个
链接点，方法是遍历整个链表直到到达表尾，但是这种方法效率很低。
像访问表头一样访问表尾的特性，使双端链表更合适于一些普通链表不方便操作的场合，
队列的实现就是这样一个情况。
双端链表增加了一个新特性：即对最后一个节点的引用，就像对第一个节点的引用一样。
 */

import sun.plugin.javascript.navig.LinkArray;

class Link2 {
    // 单数据项的链接点
    public long dData;
    public Link2 next;

    public Link2(long d) {
        dData = d;
    }

    public void displayLink() {
        System.out.print(dData + " ");
    }
}


class FirstLastList {
    private Link2 first;
    private Link2 last;

    public FirstLastList() {
        first = null;
        last = null;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public void insertFirst(long dd) {
        Link2 newLink = new Link2(dd);
        if (isEmpty())
            // 插入前链表是空的，那么必须把last指向新的链接点
            last = newLink;
        newLink.next = first;
        first = newLink;
    }

    public void insertLast(long dd) {
        Link2 newLink = new Link2(dd);
        if (isEmpty())
            // 插入前链表是空的，那么必须把first指向新的链接点
            first = newLink;
        else
            last.next = newLink;
        last = newLink;
    }

    public long deleteFirst() {
        long temp = first.dData;
        if (first.next == null)
            last = null;
        first = first.next;
        return temp;
        /*
        不幸的是，用双端链表也不能有助于删除最后一个节点，因为没有一个引用指向倒数第二个
        节点。如果最后一个节点被删除，倒数第二个节点的next字段应该变成null值。为了方便的
        删除最后一个节点，需要一个双向链表。
         */
    }

    public void displayList() {
        System.out.print("List (first --> last): ");
        Link2 current = first;
        while (current != null) {
            current.displayLink();
            current = current.next;
        }
        System.out.println();
    }
}


class FirstLastApp {

    public static void main(String[] args) {
        FirstLastList theList = new FirstLastList();

        theList.insertFirst(22);
        theList.insertFirst(44);
        theList.insertFirst(66);

        theList.insertLast(11);
        theList.insertLast(33);
        theList.insertLast(55);

        theList.displayList();

        theList.deleteFirst();
        theList.deleteFirst();

        theList.displayList();
    }
}
